Lossless variable-length source coding with codeword cost is considered forgeneral sources. The problem setting, where we impose on unequal costs on codesymbols, is called the variable-length coding with codeword cost. In thisproblem, the infimum of average codeword cost have been determined for generalsources. On the other hand, overflow probability, which is defined as theprobability of codeword cost being above a threshold, have not been consideredyet. In this paper, we determine the infimum of achievable threshold in thefirst-order sense and the second-order sense for general sources and compute itfor some special sources such as i.i.d. sources and mixed sources. Arelationship between the overflow probability of variable-length coding and theerror probability of fixed-length coding is also revealed. Our analysis isbased on the information-spectrum methods.
展开▼
